9591. Lexicography
Lucy loves
letters. At school, she learned the concept of lexicographical order and now
enjoys playing with it.
At first, she
tried to form the lexicographically smallest word from a given set of letters – it turned out to
be quite easy! Then she decided to form several words and make one of them
minimal in lexicographical order. This turned out to be much more difficult.
Formally, Lucy
wants to construct n words of length l each from the given n * l letters such
that the k-th word in the lexicographically sorted list is as small as possible in
lexicographical order.
Input. The first line contains
three integers n, l and k (1 ≤ k ≤ n ≤ 1000, 1
≤ l ≤ 1000) –
the number of
words, the length of each word, and the index of the word that Lucy wants to
minimize.
The second line contains a
string of n * l lowercase English letters.
Output. Print n words of
length l each, one word per line, using all the letters from the input.
The words must be sorted in lexicographical order, and the k-th
word must be as small as possible in lexicographical order. If there are
multiple valid answers with the same minimal k-th word, print any
of them.
|
Sample
input 1 |
Sample
output 1 |
|
3
2 2 abcdef |
ad bc ef |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
2
3 1 abcabc |
aab bcc |
SOLUTION
greedy
Algorithm analysis
In this problem,
the task is to distribute the given n * l letters
into n words
of length l, sorted
lexicographically, so that the k- th
word is as lexicographically small as possible.
The
lexicographical order of words is determined character by character from left
to right. Therefore, to minimize the k-th word, one must place the smallest
possible letters in its earliest positions (starting from the left), without
violating the lexicographical order of all words.
This
leads to the following greedy algorithm:
1. Sort all the letters of the input string in
ascending order.
2. Construct a two-dimensional array of
characters
v[1
.. n][1 .. l],
where
each row represents a separate word.
3. Fill the array column by column from left
to right, since the columns correspond to positions in the words and determine
their lexicographical order.
Filling
the first column
1. In the first column, assign letters only to
the rows with numbers from 1 to k, using
the k smallest
available letters.
2. Place these letters from top to bottom to
maintain the lexicographical order.
3. The rows numbered k + 1, …, n are
not filled at this stage, as they do not affect the minimality of the k-th
word.
This
way, we ensure that the first character of the k-th word is minimal.
Filling
the remaining columns
For
each column j = 2, 3, …, l:
1. Among the rows 1, …, k, find the
smallest index pt such that the rows pt and k match in all previous columns 1, …, j
– 1.
2. The set of rows [pt, k] consists
of all words that are indistinguishable from the k-th word on the
current prefix and therefore must remain no greater than it.
3. In column j, assign the smallest
available letters only to the rows from pt to k, from top to bottom.
4. Repeat this process until all l characters of the k-th
word are fixed.
Filling
the remaining cells
After
the k-th word has been fully constructed:
·
All
remaining letters can be distributed arbitrarily, as long as the
lexicographical order is not violated.
·
For
example, the remaining letters can be filled into the array sequentially, row
by row from top to bottom and left to right, in sorted order.
Correctness
·
In
each column, we minimize the current character of the k-th word.
·
We
assign identical or non-decreasing letters to all words that match the k-th
word on the current prefix, so the order of the words is preserved.
·
Once
the k-th word is fully constructed, no further actions can make it
larger.
Therefore,
the resulting k-th word is lexicographically minimal.
Example
Let’s
consider the following test:
6 3 6
fgahhfgaaebdcbbebc
Here,
we need to construct 6 words of length 3, using all the letters, so that the
6th word in the lexicographically sorted list is minimal.
Sort
the letters of the input string:
aaabbbbccdeeffgghh
There
are 18 = 6 ∙ 3 letters
in total, which corresponds to a 6 × 3 table.
Column
1. Fill
the first column with letters from top to bottom, from the first to the sixth
row, since the sixth row is the one we are interested in.
Column
2. Now consider the rows whose prefix matches the prefix
of the 6th row. The prefix of the 6th row after the first column is “b”.
The matching rows are 4, 5, and 6. The smallest index among them is pt =
4.
In
the second column, assign the smallest available letters to the rows numbered
from 4 to 6.
Column
3. Again,
we look for the rows whose prefix matches “bc” (after
filling the first two columns). The
matching rows are 5 and 6. The smallest index among them is pt = 5. Assign
the smallest available letters to the rows numbered from 5 to 6. Now
the 6th word is fully constructed and equals “bcd”.
Filling
the remaining letters
After
the 6th word has been fixed, the remaining letters can be distributed in any
valid way. For example, we can fill the table row by row from top to bottom and
left to right with the remaining letters in lexicographical order.
Let’s
consider the first test case:
3 2 2
abcdef
Sort
the letters of the input string:
abcdef
We
need to fill a matrix of 3 words, each of length 2, lexicographically
minimizing the 2nd word.
First,
fill the first column with letters from top to bottom, only for the rows from 1
to 2, since these are the ones that affect the minimality of the 2nd word.
Next,
move to the second column. It should be filled starting from the earliest row
whose prefix matches the prefix of the 2nd row. In this case, that row is the
2nd row itself, so pt = 2. Fill the second column with letters from row pt to row 2.
After
that, distribute the remaining letters in lexicographical order, row by row
from top to bottom and left to right, which completes the construction of a
valid answer.
Algorithm implementation
cin >> n >> l >> k;
cin >> s;
Sort the letters of the
input string. Let the current letter being processed be s[pos].
pos = 0;
sort(s.begin(), s.end());
Declare the result matrix v,
consisting of n rows and l columns, where each row corresponds to
a word of length l.
vector<string> v(n, string(l, ' '));
We’ll distribute the
letters in column j, filling the rows from pt to k – 1 inclusive (row
numbering starts from zero).
int pt = 0;
for (j = 0; j < l; j++)
{
for (i = pt; i <
k; i++)
v[i][j] = s[pos++];
Move the pointer pt
forward (pt++) until the j-th character of the (k – 1)-th row matches the j-th
character of row pt. As a result, pt points to the row with the
smallest index that currently matches the prefix of the (k – 1)-th row.
while (v[pt][j] != v[k - 1][j]) pt++;
}
After that, fill the
remaining cells of the matrix. To do this, go through the rows from top to
bottom and the columns from left to right, distributing the remaining letters.
for (i = 0; i < n; i++)
for (j = 0; j < l; j++)
if (v[i][j] == ' ') v[i][j] = s[pos++];
Print the answer.
for (i = 0; i < n; i++)
cout << v[i] << endl;